//给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 
//
// 回文字符串 是正着读和倒过来读一样的字符串。 
//
// 子字符串 是字符串中的由连续字符组成的一个序列。 
//
// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abc"
//输出：3
//解释：三个回文子串: "a", "b", "c"
// 
//
// 示例 2： 
//
// 
//输入：s = "aaa"
//输出：6
//解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 709 👎 0

package com.cute.leetcode.editor.cn;
public class PalindromicSubstrings {
    public static void main(String[] args) {
        String s = "abc";

        new PalindromicSubstrings().new Solution().countSubstrings(s);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 一个思路，使用什么尺什么法，每次搜索长度扩大
         * 这个思路倒不是不行，就是时间慢了许多，大体过程如下
         *  1.首先，所有单个的字符都可以成为回文串，所以先将字符串长度统计一下
         *  2.然后按照尺子法进行遍历，尺子长度递增递减都可以
         *      比如先看长度为2的字符串能构成回文串的有多少，判断是否为回文串的话就两个指针向中间遍历就好了
         *      然后将尺子长度增加，直到最后为字符串长度
         *  这种方法应该是可以优化的，比如可以先用最长的尺子进行遍历，这样遍历的时候其实包含了短串
         *
         *  题解中的两种方法（题解中没看到我那样写的倒是）
         *  1.动态规划法
         *      状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串
         *      状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false
         *      说明：单个字符的时候肯定是回文串，两个字符的话如果相等就是回文串
         *      多个字符的话首先要判断两边元素是否相等，相等的话就要判断去掉两边的区间内是否为回文串
         *
         *  2.中心扩展法
         *      中心扩展法需要找到所有中心点，一个字符可以是中心点，两个连续字符也可以是中心点，
         *      因为扩展的时候是向两边同时扩展，所以如果只有单个字符为中心的话永远扩展不到偶数长度字符串
         *      当前中心点是回文字符串的时候进行扩展，判断左右两个字符是否相等，相等的话更新结果并继续扩
         */
        public int countSubstrings(String s) {
            int res = s.length();
            char[] chars = s.toCharArray();
            for (int i = 1; i < s.length(); i++) {
                for (int j = 0; j < s.length()-i ; j++) {
                    boolean flag = true;
                    int left = j;
                    int right = j+i;
                    while (left<right){
                        if (chars[left]-chars[right]!=0){
                            flag =false;
                            break;
                        }
                        left++;
                        right--;
                    }
                    if (flag) res++;
                }
            }
            return res;
        }

        /**
         * 使用动态规划法实现回文字符串个数的统计，如果先遍历右边位置，再遍历左边位置就可以正常顺序写了
         * 使用dp的话一定要注意遍历顺序
         * 因为dp[i][j] 需要用到dp[i+1][j-1]，所以需要由下到上，由左到右去遍历
         */
        public int dynamicProgrammingMethod(String s){
            char[] chars = s.toCharArray();
            int len = chars.length;
            boolean[][] dp = new boolean[len][len];
            int res = 0;//统计结果
            for (int i = len-1; i >=0 ; i--) {//下到上
                for (int j = i; j < len; j++) {//左到右
                    if (chars[i] == chars[j] && (j-i < 2 || dp[i+1][j-1])){
                        res++;
                        dp[i][j] = true;
                    }
                }
            }
            return res;
        }

        /**
         * 中心扩展法，中心点一共有2*len-1个
         * 单个字符可以作为中心点，两个字符也可以作为中心点
         */
        public int centralExpansion(String s){
            int ans = 0;
            for (int i = 0; i < 2*s.length() -1 ; i++) {
                int left = i/2;//取中心点
                int right = left + i%2;//如果当前点为偶数的时候，right与left重合，不然就是连续两个中心点
                while (left >= 0 && right < s.length() && (s.charAt(left) == s.charAt(right))){
                    ans ++;
                    left--;
                    right++;
                }
            }
            return ans;
        }

        /**
         * 二刷本来想着用中心扩展的，实现起来代码比较臃肿
         */
        public int countSubstrings2(String s) {
            char[] chars = s.toCharArray();
            int len = chars.length;
            int res = len;
            boolean[][] dp = new boolean[len][len];
            //要统计一个向外扩和两个向外扩的情况
            for (int i = 0; i < len-1; i++){
                //两个向外扩展的情况
                int left = i, right = i+1;
                while (left >= 0 && right < len){
                    if (dp[left][right]) {left--;right++;}
                    else if (chars[left] != chars[right]) break;
                    else {
                        if (right-left <= 2 || dp[left+1][right-1]) {
                            res++;
                            dp[left][right] = true;
                        }
                    }
                }
                //一个向外扩展的情况
                left = i-1;right = i+1;
                while (left >= 0 && right < len){
                    if (dp[left][right]) {left--;right++;}
                    else if (chars[left] != chars[right]) break;
                    else {
                        if (right-left <= 2 || dp[left+1][right-1]) {
                            res++;
                            dp[left][right] = true;
                        }
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}